#include<iostream>
#include<stdio.h>

//快速排序
 void my_qsort(int* nums,int left,int right)
 {
    if(left>=right)
    {
        return;
    }

    int mid = (left + right) / 2;
    int key = nums[mid];
    int l = left-1,r = right+1,i = left;

    while(i<=right)
    {
        if(nums[i]<key)
        {
            std::swap(nums[i++], nums[++l]);
        }
        else if(nums[i] == key)
        {
            i++;
        }
        else
        {
            std::swap(nums[i], nums[--r]);
        }
    }

    my_qsort(nums, left, l), my_qsort(nums, r, right);
 }

 //分治排序
 void part_sort(int*nums,int left,int right)
 {
    if(left>=right)
    {
        return;
    }
    int mid = (left + right) / 2;
    part_sort(nums, left, mid), part_sort(nums, mid + 1, right);

    int temp[right - left + 1];
    int l = left, r = mid + 1, i = 0;
    while (l<=mid&&r<=right)
    {
        temp[i++] = nums[l] < nums[r] ? nums[l++] : nums[r++];
    }

    while(l<=mid)
    {
        temp[i++] = nums[l++];
    }

    while (r <= right)
    {
        temp[i++] = nums[r++];
    }

    for (int i = left; i <= right;i++)
    {
        nums[i] = temp[i - left];
    }
 }

 //堆排序

 //建大堆/小堆
 void heapify(int* nums,int parent,int n)
 {
     int largest = parent;
     int left = 2 * parent + 1;
     int right = 2 * parent + 2;

     if(left<n&&nums[largest]<nums[left])
     {
         largest = left;
     }

     if (right<n&&nums[largest] < nums[right])
     {
         largest = right;
     }

     if(largest!=parent)
     {
        std::swap(nums[largest],nums[parent]);
        heapify(nums, largest, n-1);
     }
 }

 void heapsort(int* nums,int n)
 {
    
     //建堆
     for (int i = n / 2 - 1;i>=0;i--)
     {
         heapify(nums, i, n);
     }

     //交换排序
     for (int i = n - 1; i >= 0;i--)
     {
         std::swap(nums[0], nums[i]);
         //调整
         heapify(nums, 0, i);
     }
 }

int main()
{
    int arr[10] = {2, 0, 9, 8, 3, 4, 7, 2, 5, 1};
    // my_qsort(arr, 0, sizeof(arr)/4-1);
   // part_sort(arr, 0, sizeof(arr) / 4 - 1);
    int n = sizeof(arr) / 4;
    heapsort(arr, n);
    for (int i = 0; i < sizeof(arr) / 4; i++)
    {
        printf("%d ", arr[i]);
    }
        std::cout << std::endl;
    return 0;
 
}